﻿#define _CRT_SECURE_NO_WARNINGS 
#include"work.h";
                    ////顺序表;
//void SLInit(SL* ps)
//{
//	assert(ps);
//	ps->arr = NULL;
//	ps->capacity = ps->size = 0;
//}
//void SLPrint(SL* ps)
//{
//	assert(ps);
//	int i = 0;
//	while (i < ps->size)
//	{
//		printf("%d->", ps->arr[i]);
//		i++;
//	}
//	printf("NULL\n");
//}
//void SLDestroy(SL* ps)
//{
//	assert(ps);
//	free(ps->arr);
//	ps->arr = NULL;
//	ps->capacity = ps->size = 0;
//}
//void CheckCapacity(SL* ps)
//{
//	assert(ps);
//	if (ps->capacity == ps->size)
//	{
//		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//		SLDataType* tem = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
//		assert(tem);
//		ps->arr = tem;
//		ps->capacity = newcapacity;
//	}
//}
//void SLPushFront(SL* ps, SLDataType x)
//{
//	assert(ps);
//	CheckCapacity(ps);
//	for (int i = ps->size - 1; i >= 0; i--)
//	{
//		ps->arr[i + 1] = ps->arr[i];
//	}
//	ps->arr[0] = x;
//	ps->size++;
//}
//
//void SLPushBack(SL* ps, SLDataType x)
//{
//	assert(ps);
//	CheckCapacity(ps);
//	ps->arr[ps->size] = x;
//	ps->size++;
//}
//void SLPopBack(SL* ps)
//{
//	assert(ps);
//	assert(ps->size > 0);
//	ps->size--;
//}
//void SLPopFront(SL* ps)
//{
//	assert(ps);
//	assert(ps->size > 0);
//	for (int i = 0; i < ps->size - 1; i++)
//	{
//		ps->arr[i] = ps->arr[i + 1];
//	}
//	ps->size--;
//}
//
//
//// 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。
//int removeElement(int* nums, int numsSize, int val)
//{
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (nums[i] == val)
//		{
//			for (int j = i; j < numsSize - 1; j++)
//			{
//				nums[j] = nums[j + 1];
//			}
//			i--;
//			numsSize--;
//		}
//	}
//	return numsSize;
//}
//
///// 删除排序数组中的重复项
//int removeDuplicates(int* nums, int numsSize)
//{
//	for (int i = 0; i < numsSize - 1; i++)
//	{
//		for (int j = i + 1; j < numsSize; j++)
//		{
//			if (nums[j] == nums[i])
//			{
//				for (int k = j; k < numsSize - 1; k++)
//				{
//					nums[k] = nums[k + 1];
//				}
//				j--; numsSize--;
//			}
//		}
//	}
//	return numsSize;
//}

//3. 合并两个有序数组
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//	int x = m - 1;
//	int y = n - 1;
//	int i = 1;
//	while (x >= 0 && y >= 0)
//	{
//		if (nums1[x] > nums2[y])
//		{
//			nums1[m + n - i] = nums1[x];
//			x--;
//		}
//		else
//		{
//			nums1[m + n - i] = nums2[y];
//			y--;
//		}
//		i++;
//	}
//	while (x >= 0)
//	{
//		nums1[m + n - i] = nums1[x];
//		x--;
//		i++;
//	}
//	while (y >= 0)
//	{
//		nums1[m + n - i] = nums2[y];
//		y--;
//		i++;
//	}
//}



//////////////////////////////////////单链表;

//SL* BuyNode(SLDataType x)
//{
//    SL* newnode = (SL*)malloc(sizeof(SL));
//    assert(newnode);
//    newnode->next = NULL;
//    newnode->val = x;
//    return newnode;
//}
//SL* SLInit()
//{   
//    //哨兵位
//    SL* dummy = BuyNode(-1);
//    return dummy;
//}
//
//void SLPrint(SL* ps)
//{
//    SL* pcur = ps->next;
//    while (pcur)
//    {
//        printf("%d->", pcur->val);
//        pcur = pcur->next;
//    }
//    printf("NULL\n");
//}
//void SLDestroy(SL* ps)
//{
//    SL* pcur = ps;
//    while (pcur)
//    {
//        SL* next = pcur->next;
//        free(pcur);
//        pcur = NULL;
//        pcur = next;
//    }
//}
//void SLPushBack(SL* ps, SLDataType x)
//{   
//    assert(ps);
//    SL* newnode = BuyNode(x);
//    SL* pcur = ps;
//    while (pcur->next)
//    {
//        pcur = pcur->next;
//    }
//    pcur->next = newnode;
//}
//void SLPushFront(SL* ps, SLDataType x)
//{
//    SL* newnode = BuyNode(x);
//    SL* prev = ps;
//    SL* pcur = prev->next;
//    newnode->next = pcur;
//    prev->next = newnode;
//}





//1. 删除链表中等于给定值 val 的所有结点
//typedef struct ListNode ListNode;
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* pcur = head;
//    ListNode* ptail = dummy;
//    while (pcur)
//    {
//        if (pcur->val != val)
//        {
//            ptail->next = pcur;
//            ptail = ptail->next;
//        }
//        pcur = pcur->next;
//    }
//    ptail->next = NULL;
//    ListNode* ret = dummy->next;
//    free(dummy);
//    dummy->next = NULL;
//    return ret;
//}

//2.反转链表
//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* p1 = NULL, * p2 = head, * p3 = head->next;
//    while (p2)
//    {
//        p2->next = p1;
//        p1 = p2;
//        p2 = p3;
//        if (p3)
//            p3 = p3->next;
//    }
//    return p1;
//}



//中间节点;
//typedef struct ListNode ListNode;
//struct ListNode* middleNode(struct ListNode* head)
//{
//    ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//}



//倒数第k个节点
//typedef struct ListNode ListNode;
//int kthToLast(struct ListNode* head, int k)
//{
//    ListNode* fast = head, * slow = head;
//    while (k)
//    {
//        fast = fast->next;
//        k--;
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return slow->val;
//}




//合并两个有序链表;
//typedef struct ListNode ListNode;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL && list2 == NULL)
//        return NULL;
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* ptail = dummy;
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            ptail->next = list1;
//            list1 = list1->next;
//        }
//        else
//        {
//            ptail->next = list2;
//            list2 = list2->next;
//        }
//        ptail = ptail->next;
//    }
//    if (list1)
//    {
//        ptail->next = list1;
//    }
//    if (list2)
//    {
//        ptail->next = list2;
//    }
//    return dummy->next;
//}

  //分割链表;
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* dummySmall = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* dummyBig = (ListNode*)malloc(sizeof(ListNode));
//        dummySmall->next = dummyBig->next = NULL;
//        ListNode* ptailSmall = dummySmall, * ptailBig = dummyBig;
//        ListNode* pcur = pHead;
//        while (pcur)
//        {
//            if (pcur->val < x)
//            {
//                ptailSmall->next = pcur;
//                ptailSmall = ptailSmall->next;
//            }
//            else
//            {
//                ptailBig->next = pcur;
//                ptailBig = ptailBig->next;
//            }
//            pcur = pcur->next;
//        }
//        ptailSmall->next = dummyBig->next;
//        ptailBig->next = NULL;
//        return dummySmall->next;
//    }
//};


//链表回文结构;
//ListNode* middleNode(ListNode* head)
//{
//    ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//}
//ListNode* reverseList(ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* p1 = NULL, * p2 = head, * p3 = head->next;
//    while (p2)
//    {
//        p2->next = p1;
//        p1 = p2;
//        p2 = p3;
//        if (p3)
//            p3 = p3->next;
//    }
//    return p1;
//}
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        ListNode* mid = middleNode(A);
//        ListNode* middle = reverseList(mid);
//        ListNode* pcur = A;
//        while (pcur && middle)
//        {
//            if (middle->val != pcur->val)
//                return false;
//            pcur = pcur->next;
//            middle = middle->next;
//        }
//        return true;;
//    }
//};


//相交链表;
//typedef struct ListNode ListNode;
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    int m = 0, n = 0;
//    ListNode* p1 = headA, * p2 = headB;
//    while (p1->next)
//    {
//        p1 = p1->next;
//        m++;
//    }
//    while (p2->next)
//    {
//        p2 = p2->next;
//        n++;
//    }
//    if (p1 != p2)
//        return NULL;
//    ListNode* fast = headA, * slow = headB;
//    int x = abs(m - n);
//    if (m < n)
//    {
//        fast = headB;
//        slow = headA;
//    }
//    while (x)
//    {
//        fast = fast->next;
//        x--;
//    }
//    while (fast != slow)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return fast;
//}


//环形链表;
//typedef struct ListNode ListNode;
//bool hasCycle(struct ListNode* head)
//{
//    ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}



//环形链表,返回入环第一个点;
//typedef struct ListNode ListNode;
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            ListNode* meet = slow;
//            while (head != meet)
//            {
//                head = head->next;
//                meet = meet->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}






//链表深度拷贝;
//typedef struct Node Node;
//Node* BuyNode(int x)
//{
//    Node* newnode = (Node*)malloc(sizeof(Node));
//    assert(newnode);
//    newnode->next = NULL;
//    newnode->val = x;
//    return newnode;
//}
//struct Node* copyRandomList(struct Node* head)
//{
//    if (head == NULL)
//        return NULL;
//    Node* pcur = head;
//    //复制链表;
//    while (pcur)
//    {
//        Node* next = pcur->next;
//        Node* newnode = BuyNode(pcur->val);
//        newnode->next = next;
//        pcur->next = newnode;
//        pcur = next;
//    }
//    //控制random指针;
//    pcur = head;
//    while (pcur)
//    {
//        Node* newnode = pcur->next;
//        if (pcur->random == NULL)
//        {
//            newnode->random = NULL;
//        }
//        else
//        {
//            newnode->random = pcur->random->next;
//        }
//        pcur = newnode->next;
//    }
//    //剥离链表;
//    Node* dummy = BuyNode(-1);
//    Node* ptail = dummy;
//    pcur = head;
//    while (pcur)
//    {
//        Node* newnode = pcur->next;
//        ptail->next = newnode;
//        pcur = newnode->next;
//        ptail = ptail->next;
//    }
//    return dummy->next;
//}







////////////////////////////栈;
void STInit(ST* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->arr);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
STDataType STTop(ST* ps)
{
    assert(ps);
    return ps->arr[ps->top - 1];
}
void STPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->capacity ==ps->top)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tem = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newcapacity);
        assert(tem);
        ps->arr = tem;
        ps->capacity = newcapacity;
    }
    ps->arr[ps->top] = x;
    ps->top++;
}
void STPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}



////////////////////////队列;
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
void QueuePush(Queue* pq, QDataType data)
{
    assert(pq);
    QLNode* newnode = (QLNode*)malloc(sizeof(QLNode));
    assert(newnode);
    newnode->next = NULL;
    newnode->x = data;
    if (pq->ptail == NULL)
    {
        pq->ptail = newnode;
        pq->phead = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = pq->ptail->next;
    }
    pq->size++;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    return pq->phead->x;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
    if (pq->phead->next == NULL)
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else
    {
        QLNode* del = pq->phead;
        pq->phead = pq->phead->next;
        free(del);
        del = NULL;
    }
    pq->size--;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    return pq->ptail->x;
}
int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead==NULL && pq->ptail==NULL;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QLNode* pcur = pq->phead;
    while (pcur)
    {
        QLNode* next = pcur->next;
        free(pcur);
        pcur = NULL;
        pcur = next;
    }

}



///////1.括号匹配;
//bool isValid(char* s)
//{
//    ST st;
//    STInit(&st);
//    while (*s)
//    {
//        if (*s == '(' || *s == '[' || *s == '{')
//            STPush(&st, *s);
//        else
//        {
//            if (STEmpty(&st))
//                return false;
//            char tem = STTop(&st);
//            STPop(&st);
//            if (tem == '(' && *s != ')' || tem == '[' && *s != ']' || tem == '{' && *s != '}')
//                return false;
//        }
//        s++;
//    }
//    if (!STEmpty(&st))
//        return false;
//    return true;
//}



//两个队列实现栈;
//typedef struct
//{
//    Queue q1;
//    Queue q2;
//} MyStack;
//
//
//MyStack* myStackCreate()
//{
//    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
//    assert(obj);
//    QueueInit(&obj->q1);
//    QueueInit(&obj->q2);
//    return obj;
//}
//
//void myStackPush(MyStack* obj, int x)
//{
//    if (!QueueEmpty(&obj->q1))
//        QueuePush(&obj->q1, x);
//    else
//        QueuePush(&obj->q2, x);
//}
//
//int myStackPop(MyStack* obj)
//{
//    //因为q1，q2都有可能为空，所以我们用假设法简化代码，假设q1为空；
//    Queue* empty = &obj->q1;
//    Queue* noempty = &obj->q2;
//    //如果q1不为空，假设错误，更改指针指向；
//    if (!QueueEmpty(&obj->q1))
//    {
//        empty = &obj->q2;
//        noempty = &obj->q1;
//    }
//    while (QueueSize(noempty) > 1)
//    {
//        int tem = QueueFront(noempty);
//        QueuePush(empty, tem);
//        QueuePop(noempty);
//    }
//    int ret = QueueFront(noempty);
//    QueuePop(noempty);
//    return ret;
//}
//
//int myStackTop(MyStack* obj)
//{
//    if (!QueueEmpty(&obj->q1))
//        return QueueBack(&obj->q1);
//    else
//        return QueueBack(&obj->q2);
//}
//
//bool myStackEmpty(MyStack* obj)
//{
//    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
//}
//
//void myStackFree(MyStack* obj)
//{
//    QueueDestroy(&obj->q1);
//    QueueDestroy(&obj->q2);
//    free(obj);
//}




//栈实现队列;
//typedef struct {
//    ST stpush;
//    ST stpop;
//} MyQueue;
//
//
//MyQueue* myQueueCreate()
//{
//    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//    STInit(&obj->stpop);
//    STInit(&obj->stpush);
//    return obj;
//}
//
//void myQueuePush(MyQueue* obj, int x)
//{
//    STPush(&obj->stpush, x);
//}
//
//int myQueuePop(MyQueue* obj)
//{
//    if (!STEmpty(&obj->stpop))
//    {
//        int ret = STTop(&obj->stpop);
//        STPop(&obj->stpop);
//        return ret;
//    }
//    else
//    {
//        while (!STEmpty(&obj->stpush))
//        {
//            int tem = STTop(&obj->stpush);
//            STPop(&obj->stpush);
//            STPush(&obj->stpop, tem);
//        }
//        int ret = STTop(&obj->stpop);
//        STPop(&obj->stpop);
//        return ret;
//    }
//}
//
//int myQueuePeek(MyQueue* obj)
//{
//    if (!STEmpty(&obj->stpop))
//    {
//        int ret = STTop(&obj->stpop);
//        return ret;
//    }
//    else
//    {
//        while (!STEmpty(&obj->stpush))
//        {
//            int tem = STTop(&obj->stpush);
//            STPop(&obj->stpush);
//            STPush(&obj->stpop, tem);
//        }
//        int ret = STTop(&obj->stpop);
//        return ret;
//    }
//}
//
//bool myQueueEmpty(MyQueue* obj)
//{
//    return STEmpty(&obj->stpop) && STEmpty(&obj->stpush);
//}
//
//void myQueueFree(MyQueue* obj)
//{
//    STDestroy(&obj->stpop);
//    STDestroy(&obj->stpush);
//}


//循环队列;
//typedef struct {
//    int* arr;
//    int k;
//    int head;
//    int tail;
//} MyCircularQueue;
//
//bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//bool myCircularQueueIsFull(MyCircularQueue* obj);
//MyCircularQueue* myCircularQueueCreate(int k)
//{
//    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
//    obj->head = obj->tail = 0;
//    obj->k = k;
//    return obj;
//}
//
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
//{
//    if (myCircularQueueIsFull(obj))
//    {
//        return false;
//    }
//    obj->arr[obj->tail] = value;
//    obj->tail = (obj->tail + 1) % (obj->k + 1);
//    return true;
//}
//
//bool myCircularQueueDeQueue(MyCircularQueue* obj)
//{
//    if (myCircularQueueIsEmpty(obj))
//        return false;
//    obj->head = (obj->head + 1) % (obj->k + 1);
//    return true;
//}
//
//int myCircularQueueFront(MyCircularQueue* obj)
//{
//    if (myCircularQueueIsEmpty(obj))
//        return -1;
//    return obj->arr[obj->head];
//}
//
//int myCircularQueueRear(MyCircularQueue* obj)
//{
//    if (myCircularQueueIsEmpty(obj))
//        return -1;
//    return obj->arr[(obj->tail + obj->k) % (obj->k + 1)];
//}
//
//bool myCircularQueueIsEmpty(MyCircularQueue* obj)
//{
//    return obj->head == obj->tail;
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj)
//{
//    return (obj->tail + 1) % (obj->k + 1) == obj->head;
//}
//
//void myCircularQueueFree(MyCircularQueue* obj)
//{
//    free(obj->arr);
//    obj->arr = NULL;
//    free(obj);
//    obj = NULL;
//}


/////////////堆排序以及TOPK问题;  升序建大堆，降序建小堆;
//void Print(int* a,int n)
//{
//    for (int i = 0; i < n; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    printf("\n");
//}
//void Swap(int* pa, int* pb)
//{
//    int tem = *pa;
//    *pa = *pb;
//    *pb = tem;
//}
//void AdjustDown(int* a, int parent, int size)
//{
//    int child = parent * 2 + 1;
//    while (child < size)
//    {
//        if (a[child] < a[child + 1] && child + 1 < size)
//        {
//            child++;
//        }
//        if (a[parent] < a[child])
//        {
//            Swap(&a[parent], &a[child]);
//            parent = child;
//            child = parent * 2 + 1;
//        }
//        else
//        {
//            break;
//        }
//    }
//}
//void HeapSort(int* a,int n)
//{
//    for (int i = (n - 1 - 1) / 2; i--; i >= 0)
//    {
//        AdjustDown(a, i, n);
//    }
//    int end = n - 1;
//    while (end > 0)
//    {
//        Swap(&a[0], &a[end]);
//        AdjustDown(a, 0, end);
//        end--;
//    }
//}
//
//void TopK(int* a, int k, int size)
//{    
//    //前k个数建堆;
//    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//    {
//        AdjustDown(a, i, size);
//    }
//    for (int i = k; i < size; i++)
//    {
//        if (a[i] < a[0])
//        {
//            Swap(&a[i], &a[0]);
//            AdjustDown(a, 0, k);
//        }
//    }
//}

///////////////////////////////二叉树;
//BTNode* BuyNode(BTDataType x)
//{
//    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
//    assert(newnode);
//    newnode->val = x;
//    newnode->left = newnode->right = NULL;
//    return newnode;
//}
////手搓二叉树;
//BTNode* CreatBinaryTree()
//{
//    BTNode* node1 = BuyNode(1);
//    BTNode* node2 = BuyNode(2);
//    BTNode* node3 = BuyNode(3);
//    BTNode* node4 = BuyNode(4);
//    BTNode* node5 = BuyNode(5);
//    BTNode* node6 = BuyNode(6);
//
//    node1->left = node2;
//    node1->right = node4;
//    node2->left = node3;
//    node4->left = node5;
//    node4->right = node6;
//    return node1;
//}
//void PreOrder(BTNode* root)
//{
//    if (root == NULL)
//    {
//        printf("N ");
//        return;
//     }
//    printf("%d ", root->val);
//    PreOrder(root->left);
//    PreOrder(root->right);
//}
//void InOrder(BTNode* root)
//{
//    if (root == NULL)
//    {
//        printf("N ");
//        return;
//    }
//    InOrder(root->left);
//    printf("%d ", root->val);
//    InOrder(root->right);
//}
//void PostOrder(BTNode* root)
//{
//    if (root == NULL)
//    {
//        printf("N ");
//        return;
//    }
//    PostOrder(root->left);
//    PostOrder(root->right);
//    printf("%d ", root->val);
//}
//int BinaryTreeSize(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
//}
//
//int BinaryTreeLeafSize(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//    if (root->left == NULL && root->right == NULL)
//        return 1;
//    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
//}
//
//int BinaryTreeLevelKSize(BTNode* root, int k)
//{   
//    if (root == NULL)
//        return 0;
//    if (k == 1)
//        return 1;
//    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
//}
//
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//    if (root == NULL)
//        return NULL;
//    if (root->val == x)
//        return root;
//    BTNode* tem1 = BinaryTreeFind(root->left,x);
//    if (tem1)
//        return tem1;
//    BTNode* tem2 = BinaryTreeFind(root->right, x);
//    if (tem2)
//        return tem2;
//    return NULL;
//}
//
//void BinaryTreeLevelOrder(BTNode* root)
//{   
//    if (root == NULL)
//        return;
//    Queue qu;
//    QueueInit(&qu);
//    QueuePush(&qu, root);
//    while (!QueueEmpty(&qu))
//    {   
//        BTNode* cur = QueueFront(&qu);
//        printf("%d ", cur->val);
//        if (cur->left)
//            QueuePush(&qu, cur->left);
//        if (cur->right)
//            QueuePush(&qu, cur->right);
//        QueuePop(&qu);
//    }
//}
//
//
//// 判断二叉树是否是完全二叉树
//int BinaryTreeComplete(BTNode* root)
//{
//    Queue qu;
//    QueueInit(&qu);
//    QueuePush(&qu, root);
//    int flag = 0;
//    while (!QueueEmpty(&qu))
//    {
//        BTNode* cur = QueueFront(&qu);
//        if (cur->right && !cur->left)
//            return 0;
//        if (flag && (cur->left || cur->right))
//            return 0;
//        if (cur->left)
//            QueuePush(&qu, cur->left);
//        if (cur->right)
//            QueuePush(&qu, cur->right);
//        else
//        {
//            flag = 1;
//        }
//        QueuePop(&qu);
//    }
//    QueueDestroy(&qu);
//    return 1;
//}
//// 二叉树销毁
//void BinaryTreeDestory(BTNode** root)
//{
//    if (*root)
//    {
//        BinaryTreeDestory(&(*root)->left);
//        BinaryTreeDestory(&(*root)->right);
//        free(*root);
//        *root = NULL;
//    }
//}





///////////////////单值二叉树;
//bool _isUnivalTree(struct TreeNode* root, int val)
//{
//    if (root == NULL)
//        return true;
//    if (root->val != val)
//        return false;
//    return _isUnivalTree(root->left, val) && _isUnivalTree(root->right, val);
//}
//bool isUnivalTree(struct TreeNode* root)
//{
//    if (root == NULL)
//        return true;
//    int val = root->val;
//    return _isUnivalTree(root, val);
//}




///bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
//{
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}


//int maxDepth(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    int left = maxDepth(root->left);
//    int right = maxDepth(root->right);
//    return left > right ? left + 1 : right + 1;
//}



//void _prerederTraversal(struct TreeNode* root, int* tem, int* returnSize)
//{
//    if (root == NULL)
//        return;
//    tem[*returnSize] = root->val;
//    (*returnSize)++;
//    _prerederTraversal(root->left, tem, returnSize);
//    _prerederTraversal(root->right, tem, returnSize);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize)
//{
//
//    *returnSize = 0;
//    int* tem = (int*)malloc(sizeof(int) * 300);
//    _prerederTraversal(root, tem, returnSize);
//    return tem;
//}






//对称二叉树;
//bool _isSymetric(struct TreeNode* left, struct TreeNode* right)
//{
//    if (left == NULL && right == NULL)
//        return true;
//    if (left == NULL || right == NULL)
//        return false;
//    if (left->val != right->val)
//        return false;
//    return _isSymetric(left->left, right->right) && _isSymetric(left->right, right->left);
//}
//bool isSymmetric(struct TreeNode* root)
//{
//    if (root == NULL)
//        return true;
//    return _isSymetric(root->left, root->right);
//}



//子树问题;
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
//{
//    if (root == NULL && subRoot == NULL)
//        return true;
//    if (root == NULL || subRoot == NULL)
//        return false;
//    if (isSameTree(root, subRoot))
//        return true;
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}



//插入排序;
void ArrPrint(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
//void InsertSort(int* a, int n)
//{
//    for (int i = 0; i < n-1; i++)
//    {
//        int end = i;
//        int tem = a[end + 1];
//        while (end >= 0)
//        {   
//            if (tem < a[end])
//            {
//                a[end + 1] = a[end];
//            }
//            else
//            {
//                break;
//            }
//            end--;
//        }
//        a[end + 1] = tem;
//    }
//}
//void ShellSort(int* a, int n)
//{   
//    int gap = n;
//    while (gap>1)
//    {
//        gap = gap / 3 + 1;
//        for (int i = 0; i < n - gap; i++)
//        {
//            int end = i;
//            int tem = a[end + gap];
//            while (end >= 0)
//            {
//                if (a[end] > tem)
//                {
//                    a[end + gap] = a[end];
//                }
//                else
//                {
//                    break;
//                }
//                end-=gap;
//            }
//            a[end + gap] = tem;
//        }
//    }
//}
//void ShellSort2(int* a, int n)
//{
//    int gap = n;
//    while (gap > 1)
//    {   
//        gap = gap / 3 + 1;
//        //一共有gap组
//        for (int i = 0; i < gap; i++)
//        {    
//            //一组一组排序;
//            for (int j = i; j < n - gap; j += gap)
//            {
//                int end = j;
//                int tem = a[end + gap];
//                while (end >= 0)
//                {
//                    if (a[end] > tem)
//                    {
//                        a[end + gap] = a[end];
//                    }
//                    else
//                        break;
//                    end -= gap;
//                }
//                a[end + gap] = tem;
//            }
//        }
//    }
//}
void Swap(int* x, int* y)
{
    int tem = *x;
    *x = *y;
    *y = tem;
}
//void QuickSort(int* a, int left, int right)
//{
//    if (left >= right)
//        return;
//    int begin = left, end = right;
//    int keyi = left;
//    while (begin < end)
//    {
//        while (a[end] >= a[keyi] && begin < end )
//        {
//            end--;
//        }
//        while (a[begin] <= a[keyi] && begin < end)
//        {
//            begin++;
//        }
//        Swap(&a[begin], &a[end]);
//    }
//    Swap(&a[begin], &a[left]);
//    keyi = begin;
//    QuickSort(a, left, keyi - 1);
//    QuickSort(a, keyi+1, right);
//}
//int _QuickSortNonR(int* a, int left, int right)
//{
//    int begin = left, end = right;
//    int keyi = left;
//    while (begin < end)
//    {
//        while (a[end] >= a[keyi] && begin<end)
//        {
//            end--;
//        }
//        while (a[begin] <= a[keyi] && begin < end)
//        {
//            begin++;
//        }
//        Swap(&a[begin], &a[end]);
//    }
//    Swap(&a[begin], &a[left]);
//    return begin;
//}
//void QuickSortNonR(int* a, int left, int right)
//{
//    Queue qu;
//    QueueInit(&qu);
//    QueuePush(&qu,left);
//    QueuePush(&qu, right);
//    while(!QueueEmpty(&qu))
//    {
//        int begin = QueueFront(&qu);
//        QueuePop(&qu);
//        int end = QueueFront(&qu);
//        QueuePop(&qu);
//        int keyi = _QuickSortNonR(a, begin, end);
//        //[begin,keyi-1][keyi+1,end]
//        if (begin < keyi - 1)
//        {
//            QueuePush(&qu, begin);
//            QueuePush(&qu, keyi-1);
//        }
//        if (keyi + 1 < end)
//        {
//            QueuePush(&qu, keyi + 1);
//            QueuePush(&qu, end);
//        }
//
//    } 
//}



// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int begin = left, end = right;
    int keyi = left;
    while (begin < end)
    {
        while (a[end] >= a[keyi] && begin < end)
        {
            end--;
        }
        while (a[begin] <= a[keyi] && begin < end)
        {
            begin++;
        }
        Swap(&a[begin], &a[end]);
    }
    Swap(&a[begin], &a[keyi]);
    return begin;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int hole = left;
    int ah = a[hole];
    int begin = left, end = right;
    while (begin < end)
    {
        while (a[end] >= ah && begin < end)
        {
            end--;
        }
        hole = end;
        ah = a[hole];
        while (a[begin] <= ah && begin < end)
        {
            begin++;
        }
        hole = begin;
        ah = a[hole];
    }
    a[end] = ah;
    return begin;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = PartSort1(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1,right);
}

void QuickSortNonR(int* a, int left, int right)
{
    ST st;
    STInit(&st);
    STPush(&st,left);
    STPush(&st,right);
    while (!STEmpty(&st))
    {
        int end = STTop(&st);
        STPop(&st);
        int begin = STTop(&st);
        STPop(&st);
        int keyi = PartSort1(a, begin, end);
        if (begin < keyi-1)
        {
            STPush(&st, begin);
            STPush(&st, keyi-1);
        }
        if (keyi + 1 < end)
        {
            STPush(&st, keyi + 1);
            STPush(&st, end);
        }
    }
}